#include <stdio.h>

void swap(int a[], int i, int j)
{
  int temp;
  temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

int partition(int a[], int i, int j)
/*range :[i,j], a[j] as pivot*/
{
  int m,n,pivot;
  pivot = a[j];
  m = i -1;
  for(n=i; n<j; ++n) {//range: [i,j)
    if(a[n] < pivot) {
      ++m;
      swap(a,n,m);
    }
  }
  ++m;
  swap(a,m,j);
  return m;
}

int partition2(int a[], int i, int j)
/*range :[i,j], a[j] as pivot*/
{
  int m,n,pivot;
  pivot = a[j];
  m = i;
  for(n=i; n<j; ++n) {//range: [i,j)
    if(a[n] < pivot) {
      swap(a,n,m);
      m++;
    }
  }
  swap(a,m,j);
  return m;
}
int partition3(int a[], int i, int j)
/*range: [i,j], a[i] as pivot*/
{
  int m,n,pivot;
  pivot = a[i];
  m = i;
  for(n = i+1; n<=j; ++n){//range: (i,j]
    if(a[n] < pivot){
      ++m;
      swap(a,n,m);
    }
  }
  swap(a,m,i);
  return m;
}
int partition4(int a[], int i, int j)
/*range: [i,j], a[i] as pivot*/
{
  int m,n,pivot;
  pivot = a[i];
  m = i+1;
  for(n = i+1; n<=j; ++n){//range: (i,j]
    if(a[n] < pivot){
      swap(a,n,m);
      ++m;
    }
  }
  swap(a,--m,i);
  return m;
}

int hoare_partition(int a[], int i, int j)
{
  int pivot;
  pivot = a[i];
  while(i<j){
    while(a[i]<pivot)
      ++i;
    while(a[j]>pivot)
      --j;
    swap(a,i,j);
  }
  return i;
}

void quicksort(int a[], int i, int j)
{
  int k;
  if(i >= j)
    return;
  else{ //i<j
    k = hoare_partition(a,i,j);
    quicksort(a,i,k-1);
    quicksort(a,k+1,j);
  }
}

int main(){
  int i;
  int a[] = {1,3,5,2,7,9,8,4,6,10};
  quicksort(a,0,9);

  for(i = 0; i<10; ++i)
    printf("%d\t",a[i]);
  puts("");

  return 0;
}

